package Random_Problem.Day_0202;

/**
 * @author zxc
 * @date 2023/02/02 10:13
 **/

import java.util.HashMap;

/**
 * 题目 ：统计中位数为K的子数组
 * 题目详述 ：
 * 给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。
 * 另给你一个正整数 k 。统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。
 *
 * 注意：
 * 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
 * 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
 * 子数组是数组中的一个连续部分。
 *
 * 提示：
 * n == nums.length
 * 1 <= n <= 105
 * 1 <= nums[i], k <= n
 * nums 中的整数互不相同
 *
 */
public class CountSubarrays {
    /**
     * 思路 ：
     * 核心 ：以k为中心，向两边扩展求解子数组
     * ===》
     * （1）首先，求解出值k在nums数组中下标位置index;
     * ===》 假设，大于k的数为1;同时小于k的数为-1;
     * （2）其次，从index开始，向左遍历获取，使用hashmap来记录 nums数组在index左边所有可能情况;
     * （3）最后，从index开始，向右遍历获取，变量sum存储使用可能情况;
     * ===>  即，核心在于 求解 sum + x == 0 && sum + x == 1
     * 1.即，sum + x == 0 《===》 大于k的元素个数 == 小于k的元素个数（即，元素总数为奇数;）
     * 2.即，sum + x == 1 《===》 大于k的元素个数 == 小于k的元素个数 + 1（即，元素总数为偶数;）
     *
     * @param nums
     * @param k
     * @return
     */
    public int countSubarrays(int[] nums, int k) {
        // 获取元素k在nums数组中对应下标index;
        int len = nums.length;
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (k == nums[i]) {
                index = i;
                break;
            }
        }

        int sum = 0;
        // hashmap，用来存储 元素k所有左边元素的 （>k && <k）元素的数量;
        HashMap<Integer , Integer> hashMap = new HashMap<>();
        // 特殊情况 ：有且仅有唯一元素k的时候;（初始化）
        hashMap.put(0 , 1);

        // 遍历 元素k左边的所有元素 && 使用hashmap，去存储（>k && <k）元素的数量
        for(int i = index - 1 ; i >= 0 ; i--){
            if(nums[i] > k){
                sum++;
            }
            else {
                sum--;
            }
            // 若是 sum已经存在的话，即在原本基础上对于sum所对应的value进行累加;
            // 若是 sum不存在的话，即创建 key == sum的新键值对 && 赋予value == 1;
            hashMap.put(sum , hashMap.getOrDefault(sum , 0) + 1);
        }

        // 变量countArray，用来存储 中位数为K的子数组数量;
        // 即，子数组中只包含 nums数组中 元素k的左边元素;
        int countArray = hashMap.get(0);
        if(len > 1){
            countArray += hashMap.getOrDefault(1 , 0);
        }

        sum = 0;
        // 遍历 元素k右边的所有元素;
        for(int i = index + 1 ; i < len ; i++){
            if(nums[i] > k){
                sum++;
            }
            else {
                sum--;
            }
            countArray += hashMap.getOrDefault(-sum , 0);
            countArray += hashMap.getOrDefault(1 - sum , 0);
        }
        return countArray;
    }
}
